package william.basicsort;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/1/17
 * @description 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(20, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(arr);
        System.out.println("排序后数组为: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("数组是否按照升序排列: " + ArrayUtils.isInAscOrder(arr));
    }

    /**
     * 冒泡排序
     * 针对每一轮操作,都将数组相邻的两个元素进行比较,将较大的元素交换到后面,最终最大的元素会移动到数组末尾
     * 重复上述过程,直到整个数组有序
     */
    public void bubbleSort(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length == 0) {
            return;
        }

        int N = arr.length;


        for (int i = 0; i < N; i++) {   //外层i控制是第几轮虚幻
            boolean swap = false;   //记录每轮是否有元素交换

            for (int j = 0; j < N - 1 - i; j++) {  //内层j控制对数组的遍历
                //对数组相邻元素进行两两比较,将较大的元素交换到末尾
                if (arr[j] > arr[j + 1]) {
                    ArrayUtils.swap(arr, j, j + 1);
                    swap = true;
                }
            }

            //如果本趟没有交换,说明数组已经整体有序,可以提前终止
            if (!swap) {
                return;
            }
        }
    }
}
